A packet switching communication system comprises a plurality of communicating devices, such as computers, terminals, telephones, or data sets (referred to as hosts), that are interconnected for communication through a plurality of switching networks. Connection of the hosts to the switching networks, and of the switching networks to each other, is commonly accomplished by means of communication trunks. The trunks are coupled at each end either to a host by a host access interface or to a switching network by a trunk controller.
Each switching network comprises a plurality of interconnected switching nodes that function to connect packets incoming on a trunk to the appropriate one of a number of outgoing trunks, depending upon the destination of the communication that the packets represent. Each switching node is the basic switching element of a packet switching network. The nodes are arranged and interconnected to form a switching matrix. The matrix may be thought of as divided into a plurality of columns, called stages. The nodes of a network that are the first to switch packets that have been received by the network form the first stage; the nodes that receive packets from nodes of the first stage and are the second to switch packets form the second stage; and so on. Such packet switching systems are well-known in the art. A representative packet switching system is disclosed in U.S. patent application Ser. No. 392,378, to J. S. Turner, entitled "Fast Packet Switch", filed on June 25, 1982, issued on Jan. 1, 1985, as U.S. Pat. No. 4,491,945, and assigned to the same assignee as this application.
The design and characteristics of nodes vary widely from system to system. However, a common type of node has two signal inputs and two signal outputs. A packet of signals arriving at a node input is generally buffered within the node. Based on address information carried by the packet, the packet signal stream is then directed to either one of the two node outputs. In particular, each packet includes a destination address field which carries the binary address of the destination of the packet. Each node in the packet's path through the switching network responds to the value of a different one of the address bits to switch the packet to one or the other of its outputs, thereby routing the packet along its path. (A node having more than two outputs would respond to an address element comprising a plurality of address bits.)
In order for packets to be routed properly, each node must route a packet on the basis of the correct address bit. Hence each node must know which address bit is the appropriate one for it to respond to.
The art has used for this purpose a technique called address rotation. The gist of this technique is that each node responds to the address bit which occupies the most significant bit position in a packet's destination address field, and then rotates the address by one bit position before sending the packet on to the next node. Through rotation, the bit to which the node responded becomes the least significant bit in the destination field, and the bit to which the next node should respond assumes the most significant bit position.
While effective in providing each node in a packet's path with the proper address bit, this technique suffers from certain disadvantages. First, this technique requires each node to include address rotation circuitry which often is rather complex and expensive, depending on implementation. Second, address rotation takes time and hence it slows down the progress of packets through the network. Third, if an error code such as a cyclic redundancy check (CRC) code that is computed over the whole packet, including the destination address field, is carried by a packet, address rotation changes the value of the applicable error code, and hence the code must be recomputed at each node. Consequently, each node must include error code computing circuitry, and the packet's progress through the network is further slowed down by the operation of this circuitry. And fourth, address rotation requires the packet switching system to keep track of at least two, and commonly three, different address numbers for each packet. An example will best illustrate this situation.
Assume that a packet switching network has five switching stages, and each packet has a byte-wide destination field. The physical address of the destination, as expressed in the packet's destination address field, is for example "00001101", where the rightmost five bits define the packet's route through the five stages of the network. If address rotation to the right is used, the physical address must be changed to an entry form, expressed in the destination field as "00010110", before the packet is sent through the switching network, so that rotation will provide a node in each stage with the proper address bit in the most significant--the rightmost--bit position. Upon the packet's exit from the switching network, the address will have assumed an exit form as a result of the five rotations to the right, expressed in the destination field as "10110000". As can be seen, the physical address, the entry form, and the exit form are all different.
If addresses are rotated to the left instead of to the right in the network, and the leftmost instead of the rightmost bit position is considered to be most significant, there are only two forms of the address: the physical address and the entry form, which in this example is "01101000". The exit form is the same as the physical address.
The need to keep track of a plurality of address numbers for each packet adds complexity to the system hardware and software. For example, a trunk controller that interfaces a trunk to the switching network must include circuitry for converting the physical address of a packet to the entry form before sending a packet into the switching network. It may also need to include circuitry for converting the exit form of the address into the physical address before transmitting on the trunk a packet received from the network. And the need to perform such conversions requires the trunk controller to remember the number of stages in the network, which greatly complicates the initialization of the trunk controller, and also requires changes to trunk controller software when the size of the network, in terms of the number of stages, is changed.
Furthermore, central control of the network, which is responsible for selecting call routes through the network and for setting up the routes by providing equipment such as trunk controllers with the necessary routing information, must be able to translate between the plurality of the address numbers. For this purpose, the central control must have and must maintain a plurality of address translation look-up tables, which adds overhead to the call-handling process. Use of address translation look-up tables also adversely impacts network growth: if the number of network stages changes, address look-up table entries must also change. This makes it difficult to change the networks in the field.
In summary, then, the use of address rotation adds complexity to the configuration and operation of switching systems, increases their cost, decreases their performance, and makes changes to the systems difficult to implement.